#include<cstdio>
#define cmax(a,b) (a<b?a=b:a)
#define cmin(a,b) (a>b?a=b:a)
 
typedef long long ll;
const int MAXN=810;
const ll INF=1000000000000000;
int n,d[MAXN],siz[MAXN];
ll f[2][MAXN][MAXN],g[2][MAXN];
struct edge
{
	int to[MAXN],last[MAXN],first[MAXN],tot;
	void adde(int u,int v){to[++tot]=v,last[tot]=first[u],first[u]=tot;}
}e;
void dfs(int u,int fa)
{
	for(int i=e.first[u];i;i=e.last[i])if(e.to[i]!=fa)dfs(e.to[i],u);
	register int cnt,x,i,j,k,v;
	
	for(x=1;x<=n;x++)
	{
		for(g[0][cnt=1]=0,i=e.first[u];i;i=e.last[i])if(e.to[i]!=fa)
		{
			for(j=1;j<=x&&j<=cnt+siz[v=e.to[i]];j++)
			{
				if(j<=cnt)g[1][j]=g[0][j]+f[1][v][x];
				else g[1][j]=-INF;
			}
			for(j=1;j<=cnt;j++)for(k=1;k<=siz[v]&&j+k<=x;k++)
				cmax(g[1][j+k],g[0][j]+f[0][v][k]);
			cnt+=siz[v];
			for(cmin(cnt,x),j=1;j<=cnt;j++)g[0][j]=g[1][j];
		}
		if(cnt>=x)f[0][u][x]=(ll)d[u]*x+g[0][x];
		f[1][u][x]=-INF,siz[u]=cnt;
		for(j=1;j<=cnt;j++)cmax(f[1][u][x-j],g[0][j]+(ll)d[u]*x);
	}
}
int main()
{
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	register int i,u,v;
	register ll ans=-INF;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&d[i]);
	for(u=2;u<=n;u++){
		int x,y;
		scanf("%d%d",&x,&y);
		e.adde(y,x);
		e.adde(x,y);
	}
	dfs(1,0);
	for(i=1;i<=n;i++)cmax(ans,f[0][1][i]);
	printf("%lld\n",ans);
}
